#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 6e5 + 10;
const int V = 1e6 + 1;

int n, m, ans[N];
struct node { int op, t, x, y; } p[N];
int tr[V + 10];
void reset() { memset(tr, 0x3f, sizeof tr); }
void clr(int x) { x++; for(; x <= V; x += x & -x) tr[x] = 0x3f3f3f3f; }
void add(int x, int v) { x++; for(; x <= V; x += x & -x) chkmin(tr[x], v); }
int query(int x) { int res = 1e9; x++; for(; x; x -= x & -x) chkmin(res, tr[x]); return res; }

void divide(int l, int r) {
	if(l == r) return; int mid = l + r >> 1; divide(l, mid); divide(mid + 1, r);
	int p1 = l, p2 = mid + 1;
	while(p1 <= mid && p2 <= r) {
		if(p[p1].x <= p[p2].x) (p[p1].op == 0 ? add(p[p1].y, -p[p1].x - p[p1].y) : void()), p1++;
		else (p[p2].op == 1 ? chkmin(ans[p[p2].t], p[p2].x + p[p2].y + query(p[p2].y)) : void()), p2++;
	} while(p2 <= r) (p[p2].op == 1 ? chkmin(ans[p[p2].t], p[p2].x + p[p2].y + query(p[p2].y)) : void()), p2++;
	for(--p1; p1 >= l; p1--) (p[p1].op == 0 ? clr(p[p1].y) : void());
	inplace_merge(p + l, p + mid + 1, p + r + 1, [](auto a, auto b) { return a.x == b.x ? a.y < b.y : a.x < b.x; });
}

void solve() {
	sort(p + 1, p + n + m + 1, [](auto a, auto b) { return a.t == b.t ? a.x == b.x ? a.y < b.y : a.x < b.x : a.t < b.t; });
	reset(); divide(1, n + m);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in, m = in; rep(i, 1, n) p[i].op = 0, p[i].t = 0, p[i].x = in, p[i].y = in;
	rep(i, 1, m) { p[n + i].op = in - 1; p[n + i].t = i; p[n + i].x = in; p[n + i].y = in; if(p[n + i].op == 0) ans[i] = -1; else ans[i] = 1e9; }
	solve(); rep(i, 1, n + m) p[i].x = V - p[i].x;
	solve(); rep(i, 1, n + m) p[i].y = V - p[i].y;
	solve(); rep(i, 1, n + m) p[i].x = V - p[i].x;
	solve(); rep(i, 1, m) if(ans[i] != -1) printf("%d\n", ans[i]);
	return 0;
}
